package practice_2025_8_16;

import java.util.ArrayList;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    /**
     * 计算字符串的编辑距离
     * @param args
     */
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        String t = in.next();
        s = " " + s;
        t = " " + t;
        int m = s.length();
        int n = t.length();
        int[][] dp = new int[m][n];
        // 初始化
        for(int i = 1; i < m; i++) {
            dp[i][0] = i;
        }
        for(int j = 1; j < n; j++) {
            dp[0][j] = j;
        }
        // 填表
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                if (s.charAt(i) == t.charAt(j)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        System.out.println(dp[m - 1][n - 1]);
    }


    static ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    static boolean[] vis;
    static int sum = 0;
    static int n = 0;

    /**
     * 求和 
     * @param args
     */
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        int m = in.nextInt();
        vis = new boolean[n];
        dfs(m,1, new ArrayList<>());
    }

    public static void dfs(int target, int x, ArrayList list) {
        // 递归出口
        if (sum == target) {
            res.add(list);
            for(int i = 0; i < list.size(); i++) {
                System.out.print(list.get(i) + " ");
            }
            System.out.println();
            return;
        }

        if (sum > target || x > n) {
            return;
        }
        //
        // 选
        list.add(x);
        sum += x;
        dfs(target, x + 1, list);
        // 不选
        list.remove(list.size() - 1);
        sum -= x;
        dfs(target, x + 1, list);
    }
}